1. Field of the Invention
The invention relates to a method for improving performance of algorithms relying on exponentiation using randomly generated exponents. Specifically, embodiments of the invention include a method for improving the performance of the Diffie-Hellman key-exchange protocol.
2. Background
Secure communication relies on cryptography to encode messages. In some cryptographic systems, keys are utilized to encode and decode these messages. Current cryptographic protocols perform operations on keys, such as public keys, where operands may be 512 to 1024 bits in length. It is anticipated that in the future operands may increase in size to 2048 or 4096 bits. As a result, designers of cryptographic programs and hardware must design efficient algorithms for processing these large operands for timely operation. The programs and hardware also need to be able to fit within local memory for sake of speed. Also, the larger the amount of memory required the greater the space and power consumption.
In addition to the large operands, many cryptographic programs utilize precomputed values to minimize the amount of computation needed. Multiplication and exponentiation are common operations carried out by cryptographic programs. However, using precomputed values trades processing efficiency for memory space. The larger the number and size of precomputed values the greater the speed and efficiency and the more memory that is required.
Cryptographic programs and hardware are increasingly being used in smaller devices with fewer resources. Examples of small devices include networking cards, smartcards, cellular phones and similar devices. These devices have limited resources including limited memory and processing power. Providing encryption as embedded software or hardware requires the availability of more memory and processing power which, increases the expense of these devices or results in poor performance.